package com.aqie.hard.linkedlist;

import com.aqie.easy.structure.ListNode;

import java.util.*;

/**
 * 23 合并K个排序链表
 */
public class MergeKLists {
    /**
     * 1，暴力法 O(NlogN) 22ms
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> datas = new ArrayList<>();
        // 先采集数据
        for (ListNode list : lists) {
            ListNode cur = list;
            while (cur != null) {
                datas.add(cur.val);
                cur = cur.next;
            }
        }

        // 自然排序（升序）
        Collections.sort(datas);

        // 重新组装链表
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        for(int i = 0; i < datas.size(); i ++) {
            cursor.next = new ListNode(datas.get(i));
            cursor = cursor.next;
        }

        return root.next;
    }

    /**
     * 2，优先队列  88ms
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));
        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        for (ListNode list : lists) {
            if (list != null) {
                // 这一步很关键，不能也没有必要将空对象添加到优先队列中
                priorityQueue.add(list);
            }
        }
        while (!priorityQueue.isEmpty()) {
            // 优先队列非空才能出队
            ListNode node = priorityQueue.poll();
            // 当前节点的 next 指针指向出队元素
            curNode.next = node;
            // 当前指针向前移动一个元素，指向了刚刚出队的那个元素
            curNode = curNode.next;
            if (curNode.next != null) {
                // 只有非空节点才能加入到优先队列中
                priorityQueue.add(curNode.next);
            }
        }
        return dummyNode.next;
    }



    /**
     * 3, 归并 NKlogk 9ms
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        List<ListNode> listss = Arrays.asList(lists);
        while (listss.size() > 1) {
            List<ListNode> tmp = new ArrayList<>();
            for (int i = 0; i < listss.size(); i += 2) {
                ListNode r = i == listss.size() - 1 ? null : listss.get(i + 1);
                tmp.add(merge(listss.get(i), r));
            }
            listss = tmp;
        }
        return listss.size() == 0 ? null : listss.get(0);
    }

    private ListNode merge(ListNode h1, ListNode h2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        while (h1 != null && h2 != null) {
            if (h1.val <= h2.val) {
                head.next = h1;
                h1 = h1.next;
            } else {
                head.next = h2;
                h2 = h2.next;
            }
            head = head.next;
        }
        head.next = h2 == null ? h1 : h2;
        return res.next;
    }



    /**
     * 4, 分治  4ms NlogK
     */
    public ListNode mergeKLists4(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        return mergeKLists(lists, 0, len - 1);
    }

    public ListNode mergeKLists(ListNode[] lists, int l, int r) {
        // 思考这里为什么取等于？这是因为根据下文对 mergeKLists 的递归调用情况，区间最窄的时候，只可能是左右端点重合
        if (l == r) {
            return lists[l];
        }
        int mid = (r - l) / 2 + l;
        ListNode l1 = mergeKLists(lists, l, mid);
        ListNode l2 = mergeKLists(lists, mid + 1, r);
        return mergeTwoSortedListNode(l1, l2);
    }

    private ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoSortedListNode(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoSortedListNode(l1, l2.next);
        return l2;
    }


    class Couple {
        int index;
        ListNode e;
        Couple(int index, ListNode e) {
            this.index = index;
            this.e = e;
        }
    }

    /**
     * 5. 小顶堆 O(NlogK) 22ms
     * @param lists
     * @return
     */
    public ListNode mergeKLists5(ListNode[] lists) {
        PriorityQueue<Couple> queue = new PriorityQueue<>(new Comparator<Couple>() {
            @Override
            public int compare(Couple o1, Couple o2) {
                if(o1.index == o2.index) return 0;

                if(o1.e.val == o2.e.val) {
                    return o1.index - o2.index;
                }

                return o1.e.val - o2.e.val;
            }
        });

        for(int i = 0; i < lists.length; i ++) {
            if(lists[i] != null) {
                queue.offer(new Couple(i, lists[i]));
            }
        }

        ListNode root = new ListNode(0);
        ListNode cursor = root;
        while(!queue.isEmpty()) {
            Couple node = queue.poll();
            cursor.next = node.e;
            cursor = cursor.next;
            if(node.e.next != null) {
                queue.offer(new Couple(node.index, node.e.next));
            }
        }

        return root.next;
    }


}
